package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class SerializeAndDeserializeBST {
	
	public static class Codec {

	    // Encodes a tree to a single string.
	    public String serialize(TreeNode root) {
	        if(root == null) return "";
	        LinkedList<TreeNode> stack = new LinkedList<>();
	        StringBuilder sb = new StringBuilder();
	    	stack.push(root);
	    	while(!stack.isEmpty()) {
	    		TreeNode node = stack.pop();
	    		
	    		sb.append(node.val);
	    		sb.append(',');
	    		
	    		if(node.right != null)
	    			stack.push(node.right);
	    		
	    		if(node.left != null)
	    			stack.push(node.left);
	    	}
	    	return sb.substring(0, sb.length() - 1);
	    }

	    // Decodes your encoded data to tree.
	    public TreeNode deserialize(String data) {
	    	if(data == null || data.strip().isEmpty())
	    		return null;
	    	
	    	int value = 0;
	    	TreeNode root = null, p, parent;
	    	for(int i = 0; i <= data.length(); i++) {
	    		if(i == data.length() || data.charAt(i) == ',') {
	    			
	    			if(root == null) {
	    				root = new TreeNode(value);
	    			}else {
	    				p = root;
	    				parent = null;
	    				while(p != null) {
	    					parent = p;
		    				if(value < p.val) {
		    					p = p.left;
		    				}else if(p.val < value){
		    					p = p.right;
		    				}
	    				}
	    				
	    				if(value < parent.val)
	    					parent.left = new TreeNode(value);
	    				else
	    					parent.right = new TreeNode(value);
	    			}
	    			
	    			value = 0;
	    		}else {
	    			int num = data.charAt(i) - '0';
	    			value = value * 10 + num;
	    		}
	    	}
	    	
	    	return root;
	    }
	}
}
